\section{Descrição do Sistema}
\label{sistema}

O sistema é composto por quatro módulos principais que interagem de acordo com a arquitetura apresentada na Figura~\ref{fig:arquitetura}. Esses módulos são:

\begin{description}
 \item[BD:] Responsável por armazenar as entidades de dados (Base de Dados);
 \item[CSV:] Módulo que calcula uma solução viável por meio do algoritmo de busca guloso;
 \item[AG:] Algoritmo genético, incluindo o mecanismo de evolução da população;
 \item[UI:] Interface com o usuário, por meio de linha de comando.
 \end{description}

\begin{figure}[htb]
\centering
\includegraphics[scale=1.0,bb=0 0 384 319]{arquitetura.jpg}
\caption{Arquitetura do sistema.}
\label{fig:arquitetura}
\end{figure}

\subsection{Dados do sistema}

Os dados são compostos por duas entidades: \textit{sala} e \textit{disciplina}. Cada uma destas entidades apresenta os seguintes atributos:

\paragraph{Sala:}

\begin{itemize}
 \item Nome: Identificação da sala;
 \item Capacidade: Número máximo de alunos na sala;
 \item Recursos: Recursos disponíveis (ex.: datashow, computador);
\end{itemize}

\paragraph{Disciplina:}

\begin{itemize}
 \item  Nome: Identificação da disciplina;
 \item  Tamanho: Número de matriculados;
 \item	Horário: Horário das aulas da disciplina;
 \item	Recursos: Recursos exigidos pela disciplina;
 \item	Período: Período (semestre letivo) da disciplina na grade curricular do curso.
\end{itemize}

As regras especificadas, a partir dos requisitos do problema e dos dados disponíveis, estão apresentadas na Tabela \ref{tab:regras}. Essas regras são classificadas por prioridade. Todas as regras que devem ser obrigatoriamente satisfeitas são classificadas como \textit{críticas}, enquanto as demais regras (opcionais) receberam uma prioridade de acordo com sua relevância no problema (média ou baixa). Denomina-se ``solução viável'' aquela em que todas as regras críticas são satisfeitas.

\begin{table}[t]
\centering
\caption{Regras de alocação de salas para as disciplinas.}
	\begin{tabular}{cc}
	Regra & Prioridade \\
	\hline
	Duas disciplinas não podem ocupar a mesma sala ao mesmo tempo & crítica  \\
	A sala deve oferecer os recursos adequados para a disciplina & crítica  \\
	A sala deve ter capacidade para a disciplina & crítica \\
	As disciplinas de um mesmo período devem se concentrar nas mesmas salas & média \\
	Todas as salas devem ser usadas pela mesma quantidade de disciplinas & média \\
	Cada disciplina deve ser lecionada na mesma sala & baixa \\
	\end{tabular}
\label{tab:regras}
\end{table}

\subsection{Calculador de Solução Viável}

Um aspecto inerente às regras apresentadas é que, descartadas as regras de prioridade média ou baixa, uma solução que atenda às regras críticas pode ser encontrada por meio de um algoritmo de busca guloso. Para tanto, basta gerar uma lista com os horários contínuos das disciplinas em choque e buscar atender cada um destes horários em choque sempre com uma sala distinta que melhor se encaixe (i.e. a sala de menor capacidade que satisfaz o tamanho da turma da disciplina). É importante observar que uma heurística que satisfaça todas as regras é mais complexa e implica em explorar quase todo o espaço de estados.

Nota-se, que o resultado do algoritmo de busca guloso retorna uma solução viável, porém, não necessariamente ótima. Entretanto, isto proporciona duas vantagens ao sistema de alocação de salas por disciplina: 1) É possível determinar se é necessário dispor de mais salas ou alterar o horário de uma disciplina para satisfazer o problema; 2) O algoritmo genético pode tomar uma solução viável inicial como base para a busca de uma solução ótima.

O algoritmo guloso faz parte do módulo denominado \textit{Calculador de Solução Viável} (CSV). Este módulo é responsável por fornecer ao sistema a solução viável encontrada a partir do algoritmo guloso.

\subsection{Descrição do Algoritmo Genético}

A técnica de busca com algoritmo genético, descrita na Seção~\ref{fundamentacao}, é usada na solução apresentada. As propriedades do AG aplicadas ao problema da alocação de salas são definidas a seguir.

\subsubsection{Definição dos genes}

Inicialmente, duas possíveis construções dos genes foram confrontadas: considerar cada sala como um gene ou considerar cada horário de uma disciplina como gene. A segunda opção mostrou-se mais natural, pois cada horário de uma disciplina está associado a uma única sala, enquanto o contrário não é verdadeiro: em uma sala de aula, várias disciplinas são lecionadas.

Cada indivíduo da solução é composto então de \textit{n} genes, em que \textit{n} representa o número de horários contínuos de aula de cada uma das disciplinas. Cada gene pode assumir como valor uma das salas disponíveis para alocação. Considerando, como exemplo, 2 salas disponíveis $S^{1}$ e $S^{2}$, e 3 disciplinas ofertadas: $D^{1}$, $D^{2}$, $D^{3}$, com 2 horários contínuos para cada uma (exemplo: $D^{1}$ com aulas segunda-feira e terça-feira de 8h às 10h), um possível indivíduo é mostrado na Tabela~\ref{tab:individuo}.

\begin{table}[htbp]
\centering
\caption{Exemplo de indivíduo da população para o AG utilizado.}
	\begin{tabular}{|c|c|c|c|c|c|c|}
	\hline
	\textbf{Gene} & $D^{1}$ - 1 & $D^{1}$ - 2 & $D^{2}$ - 1 & $D^{2}$ - 2  & $D^{3}$ - 1 & $D^{3}$ - 2 \\ \hline
	\textbf{Valor} & $S^{1}$ & $S^{1}$ & $S^{2}$ & $S^{2}$ & $S^{1}$ & $S^{2}$ \\ \hline
	\end{tabular}
\label{tab:individuo}
\end{table}

\subsubsection{Definição da população}

A população inicial do AG recebe então uma determinada quantidade de indivíduos. Para cada um deles, os genes são gerados aleatoriamente. Por fim, é acrescido o indivíduo obtido pelo CSV. Isto permite trabalhar, desde o início do AG, com uma solução viável. 

Um problema que surge é que há a possibilidade da mutação destruir a solução viável obtida pelo algoritmo de busca guloso. Para contornar este problema, inclui-se na seleção dos indivíduos o conceito de elitismo~\cite{elitismo}. Nela, o melhor organismo é mantido intacto na próxima geração da população.

\subsubsection{Definição da função de \textit{fitness}}

Para o sistema de alocação de salas para disciplinas, definiu-se o \textit{fitness} como uma função positiva, em que $0$ representa a solução ótima (todas as regras são satisfeitas perfeitamente), e valores maiores representam a distância que aquele indivíduo está da solução ótima.

Para calcular a distância da solução ótima, cada regra não satisfeita por um gene deve implicar no incremento do valor da \textit{função de fitness} do indivíduo.  Nota-se, que se fosse definido que cada regra tivesse o mesmo incremento, seria possível gerar um indivíduo que, ao não satisfazer apenas 2 regras de prioridade média, seria pior avaliado do que um indivíduo que quebrasse apenas uma única regra crítica. Ou seja, poderia ser descartada uma solução viável da população.

Para resolver o problema supracitado, cada regra não satisfeita incrementa, de acordo com sua prioridade, uma potência de \textit{n}, em que \textit{n} é o número de genes. Quanto mais crítica uma regra, maior a potência a ser utilizada. Assim, mesmo que uma regra de menor prioridade seja quebrada por todos os genes de um indivíduo, o sistema não interpretará o resultado como a quebra de uma regra de prioridade maior. Para o problema de alocação de salas para as disciplinas, as prioridades apresentadas na Tabela~\ref{tab:regras} podem então ser expressas numericamente por meio do incremento associado a cada uma delas (Tabela ~\ref{tab:incrementos}).

\begin{table}[htbp]
\centering
\caption{Descrição dos incrementos por prioridade para a solução proposta.}

	\begin{tabular}{cc}
	Prioridade & Incremento \\
	\hline
	Crítica & $n^{5}$ \\
	Média & $n^{4}$ \\
	Baixa & $n^{3}$ \\
	\hline
	\end{tabular}
\label{tab:incrementos}
\end{table}

